Enormous strides have been taken in recent years to develop new technologies for storing data into data-storage devices, or memories. High density and high capacity electronic memory chips have become readily and inexpensively available, and newer, three-dimensional, stacked electronic memory devices have been developed using semiconductor films. Older technologies include magnetic disks, magnetic tapes, and very old core memories and drum memories. Electronic and magnetic memory devices generally comprise a very large number of addressable physical memory locations, each physical memory location capable of storing one or more computer-readable bytes or words composed of a fixed number of bits, such as 8-bit bytes and 32-bit words or 64-bit words. The lowest-level units of storage, generally referred to as “data-storage units,” may be hierarchically grouped into larger units, such as disk sectors or three-dimensional memory planes. A physical memory location comprises one or more data-storage units that can be addressed by a physical address. A physical memory location may be a computer-readable word on one type of memory device, and a disk sector on another type of device.
In general, regardless of the technology, a certain number of the memory locations within a memory device may be defective. A defective memory location may be unreadable, or may be unreliable, producing different values when successively read without intervening write. Such defective memory locations may be identified in initial testing following manufacture, or may be dynamically identified over the lifetime of the memory device, or via incremental testing of the memory device, or by other means.
FIG. 1 shows an illustration of a three-dimensional memory. The memory comprises nine planes 101–109, each plane comprising a grid-like array of memory locations, such as memory location 110. In the three-dimensional memory device shown in FIG. 1, the memory locations on each plane are indexed like the cells in a mathematical array, starting with the memory location (0, 0) and proceeding, row by row, to memory location (31, 5). The planes may be indexed by a third index, so that each memory location specified by coordinates (x, y, z), for example, where x is the index of a row within a plane, y is the index of a column within a plane, and z is the index of a plane within the stack of planes that composes the 3-dimensional memory. In FIG. 1, a number of memory locations, or words, such as memory location 112, are shaded to indicate that the memory location is defective.
FIG. 2 illustrates one of numerous possible techniques for addressing non-defective memory locations within a memory that includes defective memory locations, such as that shown in FIG. 1. As shown in FIG. 2, a bit map 201 may be constructed to mirror the structure of the physical memory locations within the memory. For example, as shown in FIG. 2, the bit map 201 includes an array of bits, such as array 203, corresponding to each plane of the three-dimensional memory shown in FIG. 1. In each bit array, a cell, such as cell 205, includes a single bit indicating whether or not the corresponding memory location is non-defective or defective. In this figure, and in the following discussion, the bit value “0” indicates a non-defective physical memory location and the bit value “1” indicates a defective physical memory location. Note that the bit array 203 in FIG. 2 is indexed similarly to the indexing of the memory locations within the corresponding three-dimensional memory plane 101 in the memory shown in FIG. 1. The correspondence between the defective bits, shown as shaded cells in FIG. 1, and bit-value-“1”-containing cells in the bit array 203 is readily apparent.
Once a defective-memory-location map, such as the bit map 201 in FIG. 2, is prepared, the non-defective memory locations can be sequenced in monotonically increasing order by ignoring those memory locations verified as defective in the bit map. In other words, a sequence of logical, non-defective memory locations can be prepared, so that physical memory locations can be addressed using logical memory locations that are non-defective. One way to do this is to create an index 207 of the logical-memory-location address of each of the physical memory locations corresponding to the bit-map entries in the first row 209 of the bit map array. One may create a separate index, such as index 207, for each bit array corresponding to a plane in the memory. The index can be used to find a memory location close to, and preceding, a desired memory location, and then the corresponding column of the bit array can be traversed in order to find the exact physical address of the memory location within the memory. For example, if one wishes to find the physical memory location with logical memory-location address 100, one could search the index 207 to locate the cell 212 containing the logical memory-location address “98.” The index in that cell is the index of the column within the bit array having a first cell corresponding to the logical memory-location address. Thus, cell 214 within bit array 203 corresponds to a memory location having logical memory-location address “98.” Then, the column can be traversed downward, cell by cell, to locate the bit-array cell 216 corresponding to the logical memory-location address “100.” During the traverse, any bit-array cells containing the bit value “1” are skipped. Note that the difference between the contents of successive cells within the index 207 is not constant. If there are no defective memory locations within the column of a plane of the memory corresponding to a column of the bit array, then the next cell in the index is incremented by the number of cells in a column of the bit array. For example, the value “6” in the second cell 218 of the index 207 indicates that no defective memory locations occur in the first column of the first plane of the memory. However, because of the occurrence of a defective memory location in the second column of the first plane of memory (114 in FIG. 1), identified by the bit value “1” in cell 220 of the bit array 203, the value in the third cell of the index 207 222 is “11,” only five greater than the preceding value.
The index and memory-location bit map (207 and 201 in FIG. 2, respectively) represent one of many different possible methods for sequentially indexing the non-defective memory locations within a memory. Common to most methods is a bit map, such as bit map 201 in FIG. 2, in which the non-defective and defective memory locations within the memory are identified. This bit map needs to be stored in a very high-speed memory to facilitate efficient and high-speed addressing of a memory, because the bit map may need to be accessed every time a memory location is accessed. However, such high-speed memories are much more expensive than commonly employed lower-speed memories. For example, high-speed registers within a processor are generally much more quickly accessed, but are many orders of magnitude more expensive, than the lower-speed dynamic random access memories generally interconnected with the processor via one or more memory busses. Although faster operation can be obtained by including a larger number of registers within a processor, the processor becomes increasingly expensive with each added register. For these reasons, a method for efficiently storing memory-location bit maps, such as the memory-location bit map 201 shown in FIG. 2, has been recognized by manufacturers and designers of memories and by the manufacturers and users of devices that contain those memories.